#pragma once

#include <compl.h>

#ifndef SPMCLIST_HELPQUOTA
	#define SPMCLIST_HELPQUOTA (4)
#endif
#define SPMCLIST_TRY (2)

typedef struct spmcnode
{
	struct spmcnode *next;
	struct spmcnode *prev;
} spmcnode_t;

typedef struct deqreq
{
	/* 可以让其cache aligned */
	union
	{
		struct
		{
			hword_t pending : 1;
			hword_t cls : HWORD_WIDTH - 1;
			hword_t phase;
		};
		word_t state_word;
		spmcnode_t *node;
	}; // CACHE_ALIGNED;
	/* 放个helpnext */
	// struct deqreq *next_req;
} deqreq_t;
typedef CACHE_ALIGNED deqreq_t deqreq_cachealign_t;

typedef struct spmchead
{
#ifdef __amd64__
	union
	{
		struct
		{
			word_t version;
			spmcnode_t *head;
		};
		llword_t llword;
	};

#elif defined(__aarch64__)
	union
	{
		spmcnode_t *head;
		llword_t llword;
	};
#endif
// #ifdef __amd64__
// 	// struct{
// 	union
// 	{
// 		struct
// 		{
// 			// word_t volatile head_version;
// 			llword_t llword;
// 			spmcnode_t *head;
// 		};
// 		llword_t llword;
// 	};
// #elif defined(__aarch64__)
// 	// struct{
// 	union
// 	{
// 		spmcnode_t *head;
// 		llword_t llword;
// 	};
// #endif
// } ALIGN(sizeof(llword_t)) spmchead_t;
/* 改为cache行对齐能防止cache冲突 */
	// spmcnode_t sentry;	/* 放个sentry */
	// struct spmchead *next_head;	/* 下一个要遍历的目标 */
/* 同时可以放一些基本不变的信息比如下一个指针? 这样取下一个不会付出额外的遍历，也方便对队列进行调整(移除)*/
} CACHE_ALIGNED spmchead_t;

/* req能和spmchead合一吗（会增加cache miss) */
typedef struct
{
	union
	{
		spmcnode_t *head;
		llword_t llword;
	};
	spmcnode_t *tail;
} spmclist_t;

SAI void __spmcnode_head_init(spmchead_t *phead, spmcnode_t *sentry){
	sentry->next = (spmcnode_t *)NULL_PTR;
	phead->head = sentry;
}

SAI void __spmcnode_push_batch_singlen(spmcnode_t **ptail, spmcnode_t *hd, spmcnode_t *tl, spmcnode_t *next_ptr){

	spmcnode_t *cur_tail = *ptail;
	hd->prev = cur_tail;
	tl->next = next_ptr;
	atm_strel(&cur_tail->next, hd);
	*ptail = tl;
}

SAI void __spmcnode_push_batch_single(spmcnode_t **ptail, spmcnode_t *hd, spmcnode_t *tl) {
	__spmcnode_push_batch_singlen(ptail, hd, tl, (spmcnode_t *)NULL_PTR);
}

SAI void spmclist_push_batch_single(spmclist_t *l, spmcnode_t *hd, spmcnode_t *tl) {
	__spmcnode_push_batch_single(&l->tail, hd, tl);
}
/* 直接替换 */
SAI spmcnode_t *spmcnode_reclaim_all(spmchead_t *phead, spmcnode_t *sentry){
	ASSERT(sentry->next == NULL_PTR);
	spmcnode_t *ret = (spmcnode_t *)swp_rel(&phead->head, sentry);
// #ifdef __amd64__
// 	/* 版本++防止ABA */
// 	atm_st(&phead->version, phead->version + 1);
// #endif
	return ret;
}

//  pop为空, 失败
#define SPMCLIST_POP_TRY_FAILED ((spmcnode_t *)-1)

SAI bool_t __spmcnode_try_pop_lf(spmchead_t *phead, spmcnode_t **n) {
	spmcnode_t *next;
	word_t retry = 0;

	llsc_t s;
	spmcnode_t *cur_head;
	ld_link(&s, &phead->llword);
	do
	{
		cur_head = (spmcnode_t *)s.rval;
		cmb();
		next = atm_ld(&cur_head->next);
		if (!next)
		{
			*n = (spmcnode_t *)NULL_PTR;
			return TRUE;
		}
		if (st_cond(&s, (word_t)next))
		{
			*n = cur_head;
			return TRUE;
		}
	} while (++retry < SPMCLIST_TRY);
	return FALSE;
}
SAI word_t deqreq_state_pending(word_t state_word){
	return (state_word & 0x1UL);
}
SAI word_t deqreq_state_phase(word_t state_word){
	return state_word & (~0x1UL);
}
SAI bool_t deqreq_is_still_pending(word_t state_word, word_t cur_phase, word_t state_phase)
{
#ifdef USE_WFQUEUE_PROTOCOL
	PARAM_USED(state_phase);
	return (state_word & 0x1UL) && (deqreq_state_phase(state_word) <= cur_phase);
	// return (state_word & 0x1UL) && (deqreq_state_phase(state_word) == (word_t)state_phase);
#else
	PARAM_USED(cur_phase);
	return (state_word & 0x1UL) && (deqreq_state_phase(state_word) == state_phase);
#endif
}
SAI bool_t spmcnode_try_push(spmchead_t *phead, spmcnode_t *node, spmcnode_t *sentry){
	llsc_t s;
	spmcnode_t *cur_head;
	ld_link(&s, &phead->llword);

	cur_head = (spmcnode_t *)s.rval;
	/* TODO: 依赖读 */
	if (cur_head == sentry) return FALSE;
	atm_st(&node->next, cur_head);
	if (st_cond_rel(&s, (word_t)node))
	{
		/* 写入成功 */
		return TRUE;
	}
	return FALSE;
}

SAI spmcnode_t *spmcnode_help_finish_pop(spmchead_t *phead, bool_t *is_null, deqreq_t *helped_req, deqreq_t *my_req, spmcnode_t *popped_head, word_t state, word_t my_phase, hword_t help_self)
{
	PARAM_USED(my_req, help_self);

	llsc_t s = {0};
	spmcnode_t *next;
	spmcnode_t *cur_head;
	// s.ptr = NULL_PTR;
	word_t state_phase = deqreq_state_phase(state);
	while (deqreq_is_still_pending(state, my_phase, state_phase))
	{
		//
		if (popped_head)
		{

			// !快速路径?自己直接返回
			/* 使用强CAS */
			if (cas_s(&helped_req->node, (spmcnode_t **)&state, popped_head))
			{
				/* 填充完成 */
				popped_head = (spmcnode_t *)NULL_PTR;
				break;
			}
		}
		else
		{
			/* 如果每次都失败了将会在O(N^2)的时间内完成该操作 */

// ! 这里使用新版本
#ifdef USE_MSQUEUE
			if (s.ptr == NULL_PTR) ld_link(&s, &phead->llword);

			cur_head = (spmcnode_t *)s.rval;
			next = atm_ldacq(&cur_head->next);
			if (cur_head == atm_ld(&phead->head))
			{
				// 如果头部不等于尾部
				if (!next)
				{
					*is_null = TRUE;
					break;
				}
				// 连接
			}
			else
			{
				if (st_cond(&s, (word_t)next))
				{
					popped_head = cur_head;
					break;
				}
			}
			state = atm_ld(&helped_req->state_word);
// 获得节点
#else
			if (s.ptr == NULL_PTR) ld_link(&s, &phead->llword);

			cur_head = (spmcnode_t *)s.rval;
			/* TODO: 依赖读 */
			next = atm_ld(&cur_head->next);
			/* 读完加*/
			// if (cur_head != atm_ldacq(&phead->head)) {
			// 	state = atm_ld(&helped_req->state_word);
			// 	continue;
			// }
			if (!next)
			{	
				*is_null = TRUE;
				break;
			}
			if (st_cond(&s, (word_t)next))
			{
				popped_head = cur_head;
			}
			state = atm_ld(&helped_req->state_word);
#endif
		}
	}

	return popped_head;
}
// SAI spmcnode_t *__spmcnode_help_all(spmchead_t *phead, deqreq_t *a, deqreq_t *my_req)
// {
//	 word_t state;
//	 hword_t phase;
//	 deqreq_t *cur_helped;
//	 spmcnode_t *ret_node = NULL;
//	 bool_t is_null;
//	 for (word_t i = 0; i < MAX_THREADS; i++)
//	 {
//		 cur_helped = &a[i];
//		 state = atm_ld(&cur_helped->state_word);
//		 if (state & 0x1UL)
//		 {
//			 phase = state >> H__WORD_BIT;
//			 ret_node = __spmcnode_help_pop(phead, &is_null, cur_helped, my_req, ret_node, phase);
//		 }
//	 }
//	 return ret_node;
// }

// SAI spmcnode_t *__spmcnode_help(spmchead_t *phead, deqreq_t *a, bool_t *is_null, deqreq_t *my_req)
// {
//	 word_t state;
//	 hword_t phase;
//	 deqreq_t *cur_helped;
//	 hword_t last_tid = my_req->last_tid;
//	 hword_t cur_tid;
//	 spmcnode_t *ret_node = NULL;
//	 // bool_t is_null = FALSE;
//	 // #ifdef USE_WF_SPMC
//	 //	 hword_t max_tid = g_alct.max_tid;
//	 // #endif
//	 // hword_t max_tid = MAX_THREADS;
//	 for (word_t i = 0; i < MAX_HELP_ONCE; i++)
//	 {
//		 // #ifndef USE_WF_SPMC
//		 cur_tid = (last_tid + i) % MAX_THREADS;

//		 cur_helped = &a[cur_tid];
//		 state = atm_ld(&cur_helped->state_word);
//		 if (state & 0x1UL)
//		 {
//			 phase = state >> H__WORD_BIT;
//			 ret_node = __spmcnode_help_pop(phead, is_null, cur_helped, my_req, ret_node, phase);
//		 }
//		 if (*is_null)
//		 {
//			 cur_tid -= 1;
//			 break;
//		 }
//	 }

//	 // if (cur_tid > my_req->max_tid_cached)
//	 // {
//	 //	 my_req->max_tid_cached = g_alct.max_tid;
//	 //	 cur_tid = MAX_THREADS - 1;
//	 // }
//	 my_req->last_tid = cur_tid + 1;
//	 // my_req->last_tid = cur_tid;
//	 return ret_node;
// }

SAI spmcnode_t *__spmcnode_reset_req(deqreq_t *my_req)
{
	spmcnode_t *node;
	node = atm_ld(&my_req->node);
	atm_st(&my_req->node, NULL_PTR);
	return node;
}
SAI spmcnode_t *__spmcnode_reclaim_myreq(deqreq_t *my_req)
{
	word_t state = atm_ld(&my_req->state_word);
	spmcnode_t *node;
	// consumed
	if (state != 0)
	{
		node = my_req->node;
		my_req->node = (spmcnode_t *)NULL_PTR;
		return node;
	}
	return (spmcnode_t *)NULL_PTR;
}

#ifdef GLB_LIST
SAI hword_t __spmcnode_publish_deq(deqreq_t *my_req, spmchead_t *phead)
{

	hword_t phase;
	// spmcnode_t *node;

	// node = __spmcnode_check_myreq(my_req);
	//  published req

	phase = my_req->last_phase++;
	// my_req->list_ptr = phead;
	atm_st(&my_req->state_word, ((word_t)phase << H__WORD_BIT) | 0x1UL);

	return phase;
}
#endif

SAI word_t __spmcnode_publish_deq_phase(deqreq_t *my_req, spmchead_t *phead, word_t phase)
{
	PARAM_USED(phead);

	// hword_t phase;
	// spmcnode_t *node;

	// node = __spmcnode_check_myreq(my_req);
	//  published req

	// phase = my_req->last_phase++;
	// my_req->list_ptr = phead;
	word_t state = phase | 0x1UL;
	
	atm_st(&my_req->state_word, state);

	return state;
}

// SAI spmcnode_t *__spmcnode_pop_wf_predict(spmchead_t *phead, deqreq_t *a, hword_t tid)
// {
//	 spmcnode_t *node;
//	 // 节点设置为TRUE
//	 // faa phase
//	 deqreq_t *my_req = &a[tid];
//	 bool_t is_null = FALSE;
//	 hword_t phase;
//	 word_t state = atm_ld(&my_req->state_word);

//	 if (state != 0)
//	 {
//		 goto RET;
//	 }
//	 // help all threads
//	 // predictly publish
//	 phase = __spmcnode_publish_deq(my_req, phead);

//	 node = __spmcnode_help(phead, a, &is_null, my_req);
//	 // if get node, return
//	 //  提前发布
//	 // __spmcnode_publish_deq(my_req);
//	 node = __spmcnode_help_pop(phead, &is_null, my_req, my_req, node, phase);

//	 if (node)
//		 return node;
// RET:
//	 // else consumed req
//	 node = __spmcnode_reset_req(my_req);
//	 return node;
// }

// SAI spmcnode_t *__spmcnode_pop_wf(spmchead_t *phead, deqreq_t *a, hword_t tid)
// {
//	 spmcnode_t *node;
//	 // 节点设置为TRUE
//	 // faa phase
//	 deqreq_t *my_req = &a[tid];
//	 bool_t is_null = FALSE;
//	 word_t state = atm_ld(&my_req->state_word);
//	 hword_t phase;
//	 if (state != 0)
//	 {
//		 goto RET;
//	 }
//	 // help all threads
//	 node = __spmcnode_help(phead, a, &is_null, my_req);
//	 // if get node, return
//	 if (!node)
//	 {
//		 // 尝试lf
//		 // node =

//		 if (!node)
//		 {
//			 phase = __spmcnode_publish_deq(my_req, phead);
//			 node = __spmcnode_help_pop(phead, &is_null, my_req, my_req, NULL, phase);
//		 }
//	 }
//	 if (node)
//		 return node;
// RET:
//	 // else consumed req
//	 node = __spmcnode_reset_req(my_req);
//	 return node;
// }

// TODO: 备份全帮助
// SAI spmcnode_t *__spmcnode_pop_wf(spmchead_t *phead, deqreq_t *a, hword_t tid)
// {
//	 spmcnode_t *node;
//	 // 节点设置为TRUE
//	 // faa phase
//	 deqreq_t *my_req = &a[tid];

//	 word_t state = atm_ld(&my_req->state_word);

//	 if (state != 0)
//	 {
//		 goto RET;
//	 }

//	 __spmcnode_publish_deq(my_req);
//	 // help all threads
//	 node = __spmcnode_help_all(phead, a, my_req);
//	 // if get node, return
//	 if (node)
//		 return node;
// RET:
//	 // else consumed req
//	 return __spmcnode_reset_req(my_req);
// }

// SAI spmcnode_t *__spmcnode_try_pop(spmchead_t *phead)
// {
//	 spmcnode_t *next;
//	 word_t retry = 0;

//	 llsc_t s;
//	 spmcnode_t *cur_head;
//	 cmb();
//	 ld_link(&s, &phead->llword);
//	 do
//	 {
//		 // if(!cur_head) return NULL;

//		 cur_head = (spmcnode_t *)s.rval;
//		 cmb();
//		 next = atm_ld(&cur_head->next);
//		 if (!next)
//			 return NULL;
//		 if (st_cond_rel_continue(&s, (word_t)next))
//		 {
//			 return cur_head;
//		 }
//	 } while (++retry < SPMCLIST_TRY);
//	 return SPMCLIST_POP_TRY_FAILED;
// }
// 存在aba问题,使用versioned
// #ifdef __amd64__
// SAI spmcnode_t *__spmcnode_try_pop(spmchead_t *phead)
// {
// 	spmcnode_t *next;
// 	word_t retry = 0;

// 	llsc_t s;
// 	spmcnode_t *cur_head;
// 	cmb();
// 	ld_link(&s, &phead->llword);
// 	do
// 	{
// 		// if(!cur_head) return NULL;

// 		cur_head = (spmcnode_t *)s.rval;
// 		cmb();
// 		next = atm_ld(&cur_head->next);
// 		if (!next)
// 			return NULL;
// 		if (st_cond_rel_continue(&s, (word_t)next))
// 		{
// 			return cur_head;
// 		}
// 	} while (++retry < SPMCLIST_TRY);
// 	return SPMCLIST_POP_TRY_FAILED;
// }
// #else
// SAI spmcnode_t *__spmcnode_try_pop(spmchead_t *phead)
// {
// 	spmcnode_t *next;
// 	word_t retry = 0;

// 	llsc_t s;
// 	spmcnode_t *cur_head;
// 	ld_link(&s, &phead->llword);
// 	do
// 	{
// 		// if(!cur_head) return NULL;

// 		cur_head = (spmcnode_t *)s.rval;
// 		next = atm_ld(&cur_head->next);
// 		if (!next)
// 			return NULL;
// 		if (st_cond_rel_continue(&s, (word_t)next))
// 		{
// 			return cur_head;
// 		}
// 	} while (++retry < SPMCLIST_TRY);
// 	return SPMCLIST_POP_TRY_FAILED;
// }
// #endif
// SAI spmcnode_t *spmclist_try_pop(spmcl_t *l)
// {
//	 return __spmcnode_try_pop(&l->head);
// }
